// Copyright 2011 Jefferson Willian
// willmont7@gmail.com

/* dist   -> ponteiro da matriz que retorna o menor custo para 'x'                   */
/* x      -> vertice que se deseja processar o menor custo(de todos para ele)        */
void dijkstra(int matrizAdj[][MAX], int dist[], int n, int x = 0) {
  int i, j;
  pair<int, int> node;                   // node.first -> custo; node.second -> vertice
  set< pair<int, int> > processQueue;    // Fila de prioridades para o processo
  set< pair<int, int> >::iterator it;

  /* Incializa a matriz de distancia e a fila de processos */
  for (i = 0;i < n;i++) {
    dist[i] = matrizAdj[i][x];
    node.first  = dist[i];
    node.second = i;
    processQueue.insert(node);
  }

  /* Processa todos os pontos do grafo */
  while (!processQueue.empty()) {
    /* Pega o ponto de menor custo que nao foi computado */
    x = processQueue.begin()->second;
    processQueue.erase(processQueue.begin());

    /* Atualiza o melhor custo dos outros pontos passando pelo ponto 'x' */
    for (it = processQueue.begin(); it != processQueue.end(); it++) {
      i = it->second;
      /* Se existe um melhor custo entao insere o ponto com o seu novo custo na fila de processos */
      if (matrizAdj[i][x] + dist[x] < dist[i]) {
        dist[i] = matrizAdj[i][x] + dist[x];
        processQueue.erase(it);
        node.first  = dist[i];
        node.second = i;
        processQueue.insert(node);
      }
    }
  }
}
